3D point clouds are used in various image processing and computer vision applications. 3D point clouds are sets of data points in a 3D coordinate system typically representing an external surface of an object. A large number of points are measured on the surface of an object, and the obtained point cloud may be stored in a file. For computer vision applications, the 3D points are typically mapped to a recognized feature of a 2D image of the object.
Simultaneous localization and mapping (SLAM) has been extensively studied in both robotics and computer vision. SLAM refers to a problem of updating a map of an unknown environment while simultaneously localizing an observer within it. One important feature in SLAM is the relocalization, i.e. the recovery of the camera pose after a tracking failure. Since the camera pose can be estimated using correspondences between 3D points in the map and 2D features in the image, the key problem in the relocalization is to obtain the 3D-2D correspondences. The relocalization process may be considered as reversed to the mapping process: features are extracted from the 2D image and matched against those of the 3D points.
A 3D point cloud of an object or a scene may have enormous volume; it may contain millions of points. For fostering the collection of 3D-2D correspondences e.g. in SLAM, methods for obtaining binary features instead of 2D image features, thus reducing the amount of data to be processed, have been developed. A method for further speeding up feature matching is called Locality Sensitive Hashing (LSH), which is used to perform approximate nearest neighbor (ANN) search.
However, in SLAM relocalization real time performance is of critical importance, and due to the vast amount of data to be processed, the prior art methods do not provide satisfying efficiency.